Language and Automata Theory and Applications by Carlos Martín-Vide & Alexander Okhotin & Dana Shapira

Author:Carlos Martín-Vide & Alexander Okhotin & Dana Shapira
Language: eng
Format: epub
ISBN: 9783030134358
Publisher: Springer International Publishing

Proposition 10

For , let A be a DFA defined over an alphabet with n states and let be an antimorphism. Then there exists a DFA that recognizes with at most states.

Proof

We define a DFA that recognizes given a DFA A. Let . We define the DFA with the set of states

the initial state

the set of final states , and the transition function for a state and symbol with and is defined by

Informally, DFA operates by first simulating a computation of A, since by definition, we have . Once the computation reaches a final state of A, an initial state for A and is added to the current state set and the computation continues. Whenever the current state of contains a final state of A or , the initial states of both machines are added. The computation continues until the input is read and accepts if and only if a final state of A or is contained in the state of when the input has been read.

Now let us consider the state set of ,

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.